package leetcode.动态规划;

public class Leetcode1025 {
    public boolean divisorGame(int N) {
        Boolean[] dp = new Boolean[N+1];
        return dfs(N,dp);
    }

    public boolean dfs(int N,Boolean[] dp){
        if(N==1){
            return false;
        }
        if(dp[N]!=null){
            return dp[N];
        }
        for(int i = 1;i<=N/2;i++){
            if(N%i==0&&!dfs(N-i,dp)){
                return dp[N] = true;
            }
        }
        return dp[N] = false;
    }

    public boolean divisorGame1(int N) {
        boolean[] dp = new boolean[N+1];
        dp[0] = true;
        for(int i = 1;i<=N;i++){
            for(int j = 1;j<=N/2;j++){
                if(i%j ==0&&!dp[i-j]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N];
    }
}
